﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.Utils;

namespace Algoritmia.Problems.OrderStatistics
{
    public class DirectMinMaxFinder<T> : IMinMaxFinder<T>
    {
        private readonly Comparison<T> _comparison;

        public DirectMinMaxFinder(Comparison<T> comparison = null)
        {
            _comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);
        }

        #region Implementation of IMinMaxFinder<T>

        public Tuple<T, T> MinMax(IEnumerable<T> sequence)
        {
            T minimum, maximum;
            minimum = maximum = sequence.First();

            foreach(var item in sequence)
            {
                if (_comparison(item,minimum) < 0)
                {
                    minimum = item;
                }
                if (_comparison(item,maximum) > 0)
                {
                    maximum = item;
                }
            }
            return new Tuple<T, T>(minimum,maximum);
        }

        #endregion
    }

    public class MinMaxFinder<T> : IMinMaxFinder<T>
    {
        private readonly Comparison<T> _comparison;

        public MinMaxFinder(Comparison<T> comparison = null)
        {
            _comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);
        }

        #region Implementation of IMinMaxFinder<T>

        public Tuple<T, T> MinMax(IEnumerable<T> sequence)
        {
            var list = sequence.ToList();
            Func<int, int, Tuple<T, T>> f = null;
            f = (start, end) =>
                    {
                        if (end - start > 2)
                        {
                            var tpl1 = f(start, (start + end)/2);
                            var tpl2 = f((start + end)/2, end);
                            return new Tuple<T, T>(_comparison(tpl1.Item1, tpl2.Item1) < 0 ? tpl1.Item1 : tpl2.Item1,
                                                   _comparison(tpl1.Item2, tpl2.Item2) > 0 ? tpl1.Item2 : tpl2.Item2);
                        }
                        if (end - start == 2)
                        {
                            return
                                new Tuple<T, T>(
                                    _comparison(list[start], list[start + 1]) < 0 ? list[start] : list[start + 1],
                                    _comparison(list[start], list[start + 1]) > 0 ? list[start] : list[start + 1]);
                        }
                        return new Tuple<T, T>(list[start], list[start]);
                    };
            return f(0, list.Count);
        }

        #endregion
    }
}
